题面传送门：P2189 小 Z 的传感器
题目大意
在一个无向图中有 个长度为 的访问序列，问此序列是否合法，即序列中从第 个点到第 个点无需经过任何一个在 之间的点。
思路讲解
由上文可以看出，题目难点就是判断往返两点之间是否经过其他传感器点。可以有一个策略：小 Y 从序列第一个传感器点出发，走所有与其连通且不是传感器的点，看能不能到达与下一个传感器点连通的、不是传感器的点。后续再以此类推，如果都能满足就输出 Yes，反之输出 No。
看上文发现过多要素：连通、无向图，发现并查集可以做。具体思路：
- 给 之间的传感器点打标记。
- 给非传感器点和第一个传感器点进行并查集操作，进行操作时仅针对未标记点。
- 取消 号传感器点标记，进行并查集操作，进行操作时仅针对未标记点，判断它跟 号传感器点是否在一个连通块内，若不是直接判断不合法。
- 对其他传感器点做类似步骤 的操作。
代码实现
完整代码
#include<bits/stdc++.h>using namespace std;int n,m,k,q,x,y,track[100005],fa[100005],fx,fy;bool b[100005];vector<int>a[100005];int find(int x){ if(fa[x]==x) return x; return fa[x]=find(fa[x]);}int main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>n>>m>>k>>q; for(int i=1;i<=m;i++){ cin>>x>>y; a[x].push_back(y); a[y].push_back(x); } for(int z=1;z<=q;z++){ for(int i=1;i<=n;i++){ fa[i]=i; b[i]=0; } for(int i=1;i<=k;i++){ cin>>track[i]; b[track[i]]=1; } for(int i=1;i<=n;i++){ if(b[i]==1) continue; for(int j=0;j<a[i].size();j++){ if(b[a[i][j]]==0){ fx=find(i);fy=find(a[i][j]); if(fx!=fy) fa[fy]=fx; } } } for(int i=1;i<=k;i++){ b[track[i]]=0; for(int j=0;j<a[track[i]].size();j++){ if(b[a[track[i]][j]]==0){ fx=find(track[i]);fy=find(a[track[i]][j]); if(fx!=fy) fa[fy]=fx; } } if(i==1) continue; fx=find(track[i-1]);fy=find(track[i]); if(fx!=fy){ cout<<"No\n"; break; } if(fx==fy&&i==k){ cout<<"Yes\n"; } } } return 0;}